package array;

import java.util.*;

/**
 * 2561. 重排水果
 * <p>
 * 你有两个果篮，每个果篮中有 n 个水果。
 * 给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的交换成本。
 * 你想要让两个果篮相等。
 * <p>
 * 为此，可以根据需要多次执行下述操作：
 * 选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
 * 交换的成本是 min(basket1[i],basket2[j]) 。
 * 根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。
 * <p>
 * 返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。
 * <p>
 * 示例 1：
 * 输入：basket1 = [4,2,2,2], basket2 = [1,4,1,2]
 * 输出：1
 * 解释：交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果，交换的成本为 1 。
 * 此时，basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组，发现二者相等。
 * 示例 2：
 * <p>
 * 输入：basket1 = [2,3,4,1], basket2 = [3,2,5,1]
 * 输出：-1
 * 解释：可以证明无法使两个果篮相等。
 */
public class Problem_2561 {
    public static void main(String[] args) {
        int[] basket1 = {6, 6, 1, 1, 3};
        int[] basket2 = {5, 5, 2, 2, 3};
        System.out.println(new Problem_2561().minCost(basket1, basket2));
    }


    public long minCost(int[] basket1, int[] basket2) {

        // 记录每个数字出现的次数:
        // value为正数时:表示key在basket1中比basket2多出现的次数;
        // value为负数时:表示key在basket1中比basket2少出现的次数;
        Map<Integer, Integer> map = new TreeMap<>();

        // 记录最小值
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < basket1.length; i++) {
            int num = basket1[i];
            min = Math.min(min, num);
            map.put(num, map.getOrDefault(num, 0) + 1);

        }
        for (int i = 0; i < basket2.length; i++) {
            int num = basket2[i];
            min = Math.min(min, num);
            map.put(num, map.getOrDefault(num, 0) - 1);
        }

        // 需要进行交换的key
        List<Integer> merge = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int value = entry.getValue();

            // 如果相差个数是奇数个，则无法交换致最终相等
            if (entry.getValue() % 2 != 0) {
                return -1;
            } else {
                // 对于单个key需要进行交换的次数为: 相差个数value绝对值的一半
                for (int i = 0; i < Math.abs(entry.getValue()) / 2; i++) {
                    merge.add(entry.getKey());
                }
            }
        }

        Collections.sort(merge);

        long result = 0;
        // 两个成本 x1 和 x2 ，其中 x1 < x2 ,那么交换方案有两种:
        // 1. 直接交换:交换成本为 x1
        // 2. 间接交换:x1 先与两个果篮中成本最小值 m 交换,然后 x2 再与 m 交换,交换成本为 2×m

        for (int i = 0; i < merge.size() / 2; i++) {
            result += Math.min(2 * min, merge.get(i));
        }

        return result;
    }
}
